Theo truyền thuyết và thần tích ở đền thờ Hồ Đề tại làng Đông Cao thì Hồ Đề sinh ra và lớn lên tại trang Đông Cao (nay là làng Đông Cao, xã Tráng Việt, huyện Mê Linh, Hà Nội). Hồ Đề nổi tiếng là người có sức khỏe hơn người và võ nghệ cao cường. Cha nàng là Hồ Công An, là hậu duệ thứ 27 của người con thứ 48 của Lạc Long Quân và Âu Cơ. Ông đổi từ họ Hùng sang họ Hồ.[1] Vợ cả mất sớm, ông lấy vợ kế là Bạch Thị Phượng - con gái út của Lạc tướng Bạch Thái Hoa. Hồ Đề còn có một người em trai là Hồ Hác.

Vì sinh ra trong thời buổi vận nước suy vong, nhân tâm rối loạn, khắp nơi ở đâu cũng là cảnh cướp bóc và hãm hại người khác của bọn giặc xâm lược, cha mẹ Hồ Đề đã quyết tâm đào luyện võ công, binh thư và chữ nghĩa cho hai con của mình ngay từ nhỏ, để sau này dù có đi đâu hoặc gặp được Chúa công cũng có cái tài, cái đức để mà giúp đỡ cuộc đời. Hai chị em nàng khổ luyện ngày đêm và tinh thông mọi thứ từ khi còn rất trẻ.

Một hôm đẹp trời, có con ngựa đen tuyền không biết từ đâu chạy đến cửa nhà Hồ Đề. Các gia nô và mấy người buôn ngựa xúm nhau bắt lấy mà không thể nào được. Lúc này, Hồ Đề từ trong nhà đi ra xem vì nghe tiếng ồn ào bên ngoài thì thấy cảnh tượng mấy thanh niên đang vây bắt ngựa. Nàng liền bay vào dùng tay ấn đầu ngựa xuống, cầm lấy dây cương mà theo đà của ngựa liền nhảy lên lưng ngựa, giật dây cương, ngựa hí một tiếng, ngẩng cao đầu mà chạy đi. Một lúc sau, Hồ Đề dong ngựa quay lại, nét mặt vẫn tươi tỉnh như thường. Người trùm phường buôn ngựa nhìn ngắm Hồ Đề thấy tướng mạo khác thường, hỏi thì biết Hồ Đề là con nhà tướng, liền kính trọng dâng con ngựa đen ấy cho Hồ Đề.